package dynamic;

/**
 * 题目：斐波那契数列
 * 求斐波那契数列的第 n 项，n <= 39。
 *
 * @Author Gavin
 * @date 2022.05.02 23:00
 */
public class solution_11 {
    //Time:O(n),Space:O(n)
    public int solution_1(int n) {
        if (n <= 1)
            return n;
        int[] fib = new int[n + 1];
        fib[1] = 1;
        for (int i = 2; i <= n; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        return fib[n];
    }
    //Time:O(n),Space:O(1)
    public int solution_2(int n) {
        if (n <= 1)
            return n;
        //由于只关注前一个和前两个数的值，所以可以直接使用两个变量就可以了。
        int pre2 = 0, pre1 = 1;
        int fib = 0;
        for (int i = 2; i <= n; i++) {
            fib = pre2 + pre1;
            pre2 = pre1;
            pre1 = fib;
        }
        return fib;
    }

    //题目的要求是n<39,所以可以初始化的时候就计算好，这样在获取的时候就可以O(1)时间获取
    private int[] fib = new int[40];
    public solution_11() {
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
    }
    public int solution_3(int n) {
        return fib[n];
    }
}
